package trainer;
import java.util.*;
public class HashSort {
	
	ArrayList<Double> nA = new ArrayList<Double>();
	ArrayList<String> nA2 = new ArrayList<String>();
	
	public ArrayList<Double> getSort(ArrayList<Double> nArray){
		
		for(Double n:nArray){
			nA.add(n);
		}
		qsort(nA.get(0).doubleValue(),0,nA.size()-1);
		return nA;
	}
	
	public void qsort(double nPivot,int nBegin, int nEnd){
		if(nEnd<=nBegin){
			
			
		}else{
			int nHead = nBegin;
			int nTail = nEnd;
			while((nHead<nTail)){
				while((nA.get(nHead).doubleValue()<nPivot)&&(nHead<nEnd)){
					nHead++;
				}
				while((nA.get(nTail).doubleValue()>=nPivot)&&(nTail>nBegin)){
					nTail--;
				}
				if(nHead<nTail){
				double nTmp = nA.get(nHead).doubleValue();
				String nTmp2 = nA2.get(nHead);
				nA.set(nHead, nA.get(nTail));
				nA2.set(nHead,nA2.get(nTail));
				nA.set(nTail,nTmp);
				nA2.set(nTail, nTmp2);
				
				}
			}
			
			if((nTail-1)>=nBegin)
			   qsort(nA.get(nBegin).doubleValue(),nBegin,nTail);
			if((nTail+1)<=nEnd)
			   qsort(nA.get(nTail+1).doubleValue(),nTail+1,nEnd);
		}
	}
	
   public  ArrayList<String> HashSort(HashMap<String,Double> srcMap,String order){
	   ArrayList<String> resultMap = new ArrayList<String>();	   
	   Iterator it = srcMap.keySet().iterator();
	   ArrayList<String> leftMap = new ArrayList<String>();
	   ArrayList<Double> rightMap = new ArrayList<Double>();
	   while(it.hasNext()){
		   String key = (String) it.next();
		   nA2.add(key);
		   nA.add(srcMap.get(key));		   
	   }
	   this.qsort(nA.get(0).intValue(),0,nA.size()-1);
	   if(order.equalsIgnoreCase("r")){
		   for(int i=nA2.size()-1;i>-1;i--){
			   resultMap.add(nA2.get(i)+" "+String.valueOf(nA.get(i).doubleValue()));
		   }
	   }else{
		   for(int i=0;i<nA2.size();i++){
			   resultMap.add(nA2.get(i)+" "+String.valueOf(nA.get(i).doubleValue()));
		   }
	   }
	   
	   return resultMap;
   }
   
   public ArrayList<String> HashBSort(HashMap<String,Double> srcMap,String order){
	   ArrayList<String> sorted = new ArrayList<String>();
	   String[] keys=new String[srcMap.size()];
	   double[] values=new double[srcMap.size()];
	   Iterator it = srcMap.keySet().iterator();
	   int n=0;
	   while(it.hasNext()){
		   String key = (String) it.next();
		   double dValue = srcMap.get(key).doubleValue();
		   keys[n]=key;
		   values[n]=dValue;
		   n++;
	   }
	   for(int i=0;i<srcMap.size();i++){
		   for(int j=0;j<srcMap.size()-1;j++){
			   if(values[j]>values[j+1]){
				   double dtmp = values[j+1];
				   values[j+1]=values[j];
				   values[j] = dtmp;
				   String stmp = keys[j+1];
				   keys[j+1]=keys[j];
				   keys[j] = stmp;
			   }
		   }
	   }
	   if(order.equalsIgnoreCase("r")){
		   for(int i=srcMap.size()-1;i>0;i--){
			   sorted.add(keys[i]+" "+values[i]);
		   }
	   }else{
		   for(int i=0;i<srcMap.size();i++){
			   sorted.add(keys[i]+" "+values[i]);
		   }
	   }
	   
	   return sorted;
   }
}
